#include "common.h"

template<class ElemType>
struct node {
	ElemType data;
	struct node* next;
};

typedef node<int> LNode, *LinkList;

//头插法初始化链表
void initList_HeadInsert(LinkList& L) {
	LinkList s;
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;
	scanf("%d", &x);
	while (x!= 9999) {
		s = (LinkList)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
		scanf("%d", &x);
	}
}


//初始化一个空的单链表,不带头结点
bool initList_NoHead(LinkList& L) {
	L = NULL;
	return true;
}

//初始化一个空的单链表,带头结点
bool initList_Head(LinkList& L) {
	L = (LinkList)malloc(sizeof(LNode));
	if (L == NULL) {
		return false;
	}
	return true;
}

void list_TailInsert(LinkList& L) {
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	LNode* s, * r = L;
	scanf("%d", &x);
	while (x != 9999) {
		s = (LinkList)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
		scanf("%d", &x);
	}
	r->next = NULL;
}

//后插操作 时间复杂度O(1)
bool insertNextNode(LinkList p, int e) {
	if (p == NULL)
		return false;
	LinkList s = (LinkList)malloc(sizeof(LNode));
	if (s == NULL)
		return false;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

//前插操作 时间复杂度O(1)
bool insertPriorNode(LinkList p, int e) {
	if (p == NULL)
		return false;
	LinkList s = (LinkList)malloc(sizeof(LNode));
	if (s == NULL)
		return false;
	s->next = p->next;
	p->next = s;
	s->data = p->data;
	p->data = e;
	return true;
}

bool listInsert_NoHead(LinkList& L, int i, int e) {
	if (i < 1) 
		return false;
	if (i == 1) {
		LinkList s = (LinkList)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;
		L = s;
		return false;
	}
	LinkList p;
	int j = 1;
	p = L;
	while (p != NULL && j < i - 1) {
		p = p->next;
		j++;
	}
	return insertNextNode(p, e);
}

//带头结点的插入
bool listInsert_Head(LinkList& L, int i, int e) {
	if (i < 1)
		return false;
	LinkList p;
	int j = 0;
	p = L;
	while (p != NULL && j < i - 1) {
		p = p->next;
		j++;
	}
	return insertNextNode(p, e);
}

//删除操作
bool listDelete(LinkList& L, int i, int& e) {
	if (i < 1)
		return false;
	LinkList p;
	int j = 0;
	p = L;
	while (p != NULL && j < i - 1) {
		p = p->next;
		j++;
	}
	if (p == NULL) //i值不合法
		return false;
	if (p->next == NULL) //第i-个结点之后已无其他结点
		return false;
	LinkList q = p->next;
	e = q->data;
	p->next = q->next;
	free(q);
	return true;
}

//删除指定结点p，但是如果在最后一个结点后会出现bug
bool deleteNode(LinkList p) {
	if (p == NULL)
		return false;
	LinkList q = p->next;
	p->data = q->data;
	p->data = p->next->data;
	free(q);
	return true;
}

//按位查找，返回第i个元素（带头结点）
LNode* getElem(LinkList L, int i) {
	if (i < 0)	//如果位序错误
		return NULL;
	LNode* p = NULL;
	int j = 0;
	p = L;
	while (p != NULL && j < i) {
		p = p->next;
		j++;
	}
	return p;
}

//按值查找，找到数据域==e的结点
LNode* locataElem(LinkList L, int e) {
	LNode* p = L->next;
	while (p != NULL && p->data != e)
		p = p->next;
	return p;	//找到返回该指针，否则返回null
}

//求表长度
int listLength(LinkList L) {
	int len = 0;
	LNode* p = L;
	while (p->next != NULL) {
		p = p->next;
		len++;
	}
	return len;
}

//链表的逆置
void reverseList(LinkList L) {
	int i, len = listLength(L);
	LinkList p, q;
	p = L->next;
	for (i = 0; i < len - 1; i++) {
		q = p->next;
		p->next = q->next;
		q->next = L->next;
		L->next = q;
	}
}

bool empty(LinkList L) {
	return (L == NULL);
}

void print(LinkList L) {
	LinkList p = L->next;
	while (p != NULL) {
		cout << p->data;
		p = p->next;
	}
	cout << endl;
}